We develop robust and scalable methods to uncover global properties of communities hidden in large noisy networks. Consider the fundamental situation where the nodes or users in the network are split into two classes according to their opinion or preferences on a specific topic. Examples include support of a particular candidate in elections [1], or a level of interest in a particular topic, or a degree of support of certain statement. We call these two classes the "active" and "inactive" users, respectively. Motivated by real-world settings, we assume that the network of interest is too large to be processed manually, especially for each possible topic of interest. Therefore, activity observations of users are determined and delivered to us by a third-party algorithm called the crawler. Naturally, the crawler has its classification and learning errors that are not known to us. Therefore, we treat a general nonparametric case of the crawler error probabilities. Our goal is to learn global properties of communities of active and inactive users despite such noise and errors, in an unsupervised way, while additionally being robust to a strong adversary.

Cryo-electron microscopy (cryo-EM) is an emerging experimental method to characterize the structure of large biomolecular assemblies. Single particle cryo-EM records 2D images (so-called micrographs) of projections of the three-dimensional particle, which need to be processed to obtain the three-dimensional reconstruction. A crucial step in the reconstruction process is particle picking which involves detection of particles in noisy 2D micrographs with low signal-to-noise ratios of typically 1:10 or even lower. Typically, each picture contains a large number of particles, and particles have unknown irregular and nonconvex shapes.

We develop a novel method for detection of signals and reconstruction of images in the presence of random noise. The method uses results from percolation theory. We specifically address the problem of detection of multiple objects of unknown shapes in the case of nonparametric noise. The noise density is unknown and can be heavy-tailed. The objects of interest have unknown varying intensities. No boundary shape constraints are imposed on the objects, only a set of weak bulk conditions is required. We view the object detection problem as a multiple hypothesis testing for discrete statistical inverse problems. We present an algorithm that allows to detect greyscale objects of various shapes in noisy images. We prove results on consistency and algorithmic complexity of our procedures. Applications to cryo-electron microscopy are presented.